#include "jarvis.h"

/*! \file jarvis.c
 * \author A. POLI
 * \date 2011
 */


vertex recuperation_min_vertex(vertex* tab)
{
  vertex temp = tab[0];
  int i;
  for(i=1;i<nbPoints;i++)
  {
    if(temp.coords[0]>tab[i].coords[0])
    {
      temp = tab[i];
    }else if(temp.coords[0]==tab[i].coords[0])
      if(temp.coords[1]>tab[i].coords[1])
      {
	temp = tab[i];
      }
  }
  return temp;
}

int recuperation_min_position(vertex* tab)
{
  vertex temp = tab[0];
  int indice = 0,i;
  for(i=1;i<nbPoints;i++)
  {
    if(temp.coords[0]>tab[i].coords[0])
    {
      temp = tab[i];
      indice = i;
    }else if(temp.coords[0]==tab[i].coords[0])
      if(temp.coords[1]>tab[i].coords[1])
      {
	temp = tab[i];
	indice = i;
      }
  }
  return indice;
}

/*!  TODO : regarder le sens !
retourne le plus grand vertex entre b et c si a b c sont alignes
*/
vertex orientation(vertex a,vertex b,vertex c)
{
    int alignes=sont_alignes(a,b,c);
    if(alignes == 0)
    {
        return plus_grand_vertex(b,c);
    }

}

int egalite_vertex(vertex a, vertex b)
{
    if((a.coords[0]==b.coords[0]) && (a.coords[1]==b.coords[1]))
        return 1;
    else
        return 0;
}


envConv jarvis(vertex *tab)
{
  vertex pMin = recuperation_min_vertex(tab);
  int pIndice = recuperation_min_position(tab);
  int IndiceEnvConv = 0;
  envConv tableau;
  int pMin_retour = 0;
  int i;
  tableau[IndiceEnvConv] = pMin;
  vertex suivant = tab[pIndice+1];

    while(pMin_retour == 0){
        for(i=0;i<nbPoints;i++)
        {
            if(sont_alignes(pMin,suivant,tab[i]) == 1)
            {
                suivant=tab[i];
            }
        }
        if(egalite_vertex(suivant,pMin))
        {
            pMin_retour = 1;
        }else{
            IndiceEnvConv++;
            tableau[IndiceEnvConv] = suivant;
        }
    }
    return tableau;
}
